package leetcode_61_80;

import java.util.ArrayList;
import java.util.List;

public class fullJustify_68 {
    /**
     * 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词
     * 使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
     * 每个单词的长度大于 0，小于等于 maxWidth。
     * 要求：
     * 1，尽可能多地往每行中放置单词。
     * 2，必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
     * 3，如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数
     *
     *
     * 0ms,虽然代码看起来繁琐了些
     * @param words
     * @param maxWidth
     * @return
     */
    public List<String> fullJustify(String[] words, int maxWidth) {
        for (int i = 0;i < words.length;) {
            int start=i; //记录该行起始单词
            int spare=maxWidth;    //该行剩余空间
            int wordNum=0,spaceNum=0; //该行几个单词，几个空格
            for (int t = i ; t<words.length && spare >=words[t].length();t++,i++) {  //每行计算单词和空格数量
                wordNum++;
                spare-=words[t].length();
                if (spare > 0) { //需要填充空格
                    spaceNum++;
                    spare--;
                }
            }
            spaceNum+=spare;
            int minSpaceNum=  wordNum !=1 ?  spaceNum/(wordNum-1) : 0//每行单词间空格最少几个和其数量，若只有一个单词则直接赋值0
                 ,maxCount=  wordNum !=1  ?  spaceNum- (wordNum-1)*minSpaceNum : 0//每行单词间空格最多几个和其数量
                 ,minCount=wordNum-1-maxCount;
            StringBuilder minSpace=new StringBuilder();
            StringBuilder maxSpace=new StringBuilder();
            //预先处理好空格
            if (i == words.length) { //当处理最后一行时，间隔只能有一个空格，特殊处理一下
                minCount = wordNum - 1;
                maxCount=0;
                minSpace.append(" ");
            } else {
                for (int j = 0; j < minSpaceNum; j++)
                    minSpace.append(" ");
                if (maxCount != 0) {
                    maxSpace.append(minSpace).append(" ");
                }
            }
            ans.add(fullWords(words,start,i-1,maxSpace,maxCount,minSpace,minCount,maxWidth).toString());
        }
        return ans;
    }
    List<String>ans=new ArrayList<>();
    public StringBuilder fullWords(String[] words, int start,int end,StringBuilder maxSpace,int maxCount,StringBuilder minSpace,int minCount,int maxWidth) {
        StringBuilder s = new StringBuilder();
        for(int i=start;i<=end;i++){
            s.append(words[i]);
            if(maxCount!=0){               //先加多的空格
                s.append(maxSpace);
                maxCount--;
            } else if(minCount!=0){
                s.append(minSpace);
                minCount--;
            }
        }
        //特殊情况需要补齐空格
        for(int j=s.length();j<maxWidth;j++)
                s.append(" ");
        return s;
    }
}
